Permutations via linear translators

We show that many infinite classes of permutations over finite fields can be constructed via translators with a large choice of parameters. We first characterize some functions having linear translators, based on which several families of permutations are then derived. Extending the results of [9], we give in several cases the compositional inverse of these permutations. The connection with complete permutations is also utilized to provide further infinite classes of permutations. Moreover, we propose new tools to study permutations of the form $x\mapsto x+{(x^{p^m}-x+\delta )}^s$ and a few infinite classes of permutations of this form are proposed.     

Variational Bayes With Intractable Likelihood

Variational Bayes (VB) is rapidly becoming a popular tool for Bayesian inference in statistical modeling. However, the existing VB algorithms are restricted to cases where the likelihood is tractable, which precludes their use in many interesting situations such as in state--space models and in approximate Bayesian computation (ABC), where application of VB methods was previously impossible. This article extends the scope of application of VB to cases where the likelihood is intractable, but can be estimated unbiasedly. The proposed VB method therefore makes it possible to carry out Bayesian inference in many statistical applications, including state--space models and ABC. The method is generic in the sense that it can be applied to almost all statistical models without requiring too much model-based derivation, which is a drawback of many existing VB algorithms. We also show how the proposed method can be used to obtain highly accurate VB approximations of marginal posterior distributions. Supplementary material for this article is available online.     

Gabor systems and almost periodic functions

Inspired by results of Kim and Ron, given a Gabor frame in $L^2(\mathbb{R})$, we determine a non-countable generalized frame for the non-separable space ${\mathit{AP}}_2(\mathbb{R})$ of the Besicovic almost periodic functions. Gabor type frames for suitable separable subspaces of ${\mathit{AP}}_2(\mathbb{R})$ are constructed. We show furthermore that Bessel-type estimates hold for the AP norm with respect to a countable Gabor system using suitable almost periodic norms of sequences.     

Low rank matrix recovery from rank one measurements

We study the recovery of Hermitian low rank matrices $X\in {\mathbb{C}}^{n\times n}$ from undersampled measurements via nuclear norm minimization. We consider the particular scenario where the measurements are Frobenius inner products with random rank-one matrices of the form $a_j{a}_j^{?}$ for some measurement vectors $a_1,\dots ,a_m$, i.e., the measurements are given by $b_j=\mathrm{tr}(X{a}_j{a}_j^{?})$. The case where the matrix $X=x{x}^{?}$ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements $b_j=|〈x,a_j〉{|}^2$) via the PhaseLift approach, which has been introduced recently. We derive bounds for the number m of measurements that guarantee successful uniform recovery of Hermitian rank r matrices, either for the vectors $a_j$, $j=1,\dots ,m$, being chosen independently at random according to a standard Gaussian distribution, or $a_j$ being sampled independently from an (approximate) complex projective t-design with $t=4$. In the Gaussian case, we require $m\ge Crn$ measurements, while in the case of 4-designs we need $m\ge \mathit{Cr}n\log ?(n)$. Our results are uniform in the sense that one random choice of the measurement vectors $a_j$ guarantees recovery of all rank r-matrices simultaneously with high probability. Moreover, we prove robustness of recovery under perturbation of the measurements by noise. The result for approximate 4-designs generalizes and improves a recent bound on phase retrieval due to Gross, Krahmer and Kueng. In addition, it has applications in quantum state tomography. Our proofs employ the so-called bowling scheme which is based on recent ideas by Mendelson and Koltchinskii.     

Approximations in Sobolev spaces by prolate spheroidal wave functions

Recently, there is a growing interest in the spectral approximation by the Prolate Spheroidal Wave Functions (PSWFs) ${\psi }_{n,c},c>0$. This is due to the promising new contributions of these functions in various classical as well as emerging applications from Signal Processing, Geophysics, Numerical Analysis, etc. The PSWFs form a basis with remarkable properties not only for the space of band-limited functions with bandwidth c, but also for the Sobolev space $H^s([?1,1])$. The quality of the spectral approximation and the choice of the parameter c when approximating a function in $H^s([?1,1])$ by its truncated PSWFs series expansion, are the main issues. By considering a function $f\in H^s([?1,1])$ as the restriction to $[?1,1]$ of an almost time-limited and band-limited function, we try to give satisfactory answers to these two issues. Also, we illustrate the different results of this work by some numerical examples.     

Tight Heffter Arrays Exist for all Possible Values

A tight Heffter array is an matrix with nonzero entries from such that (i) the sum of the elements in each row and each column is 0, and (ii) no element from appears twice. We prove that exist if and only if both m and n are at least 3. If H has the property that all entries are integers of magnitude at most , every row and column sum is 0 over the integers, and H also satisfies ), we call H an integer Heffter array. We show integer Heffter arrays exist if and only if . Finally, an integer Heffter array is shiftable if each row and column contains the same number of positive and negative integers. We show that shiftable integer arrays exists exactly when both are even.     

New upper bounds for online strip packing

In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into one or more strips of width 1 and infinite height so as to minimize the required height of the packing. By analyzing a two-phase shelf algorithm, we derive a new upper bound 6.4786 on the competitive ratio for online one strip packing. This result improves the best known upper bound of 6.6623. We also extend this algorithm to online multiple strips packing and present some numeric upper bounds on their competitive ratios which are better than the previous bounds.     

Quadratic cone cutting surfaces for quadratic programs with on–off constraints

We study the convex hull of a set arising as a relaxation of difficult convex mixed integer quadratic programs (MIQP). We characterize the extreme points of the convex hull of the set and the extreme points of its continuous relaxation. We derive four quadratic cutting surfaces that improve the strength of the continuous relaxation. Each of the cutting surfaces is second-order-cone representable. Via a shooting experiment, we provide empirical evidence as to the importance of each inequality type in improving the relaxation. Computational results that employ the new cutting surfaces to strengthen the relaxation for MIQPs arising from portfolio optimization applications are promising.